package com.LeeCode;

import java.util.Arrays;

/**
 * 最大化城市的最小电量
 */

public class Code2528 {
    public static void main(String[] args) {
        int[] stations = {4, 2};
        int r = 1, k = 1;
        System.out.println(new Code2528().maxPower(stations, r, k));
    }

    public long maxPower(int[] stations, int r, int k) {
        long[] powers = new long[stations.length + 1];
        for (int i = 0; i < stations.length; i++) {
            int start = Math.max(0, i - r), end = Math.min(stations.length - 1, i + r);
            powers[start] += stations[i];
            powers[end + 1] -= stations[i];
        }

        long left = 0, right = Long.MAX_VALUE;


        while (left + 1 < right) {
            long mid = left + (right - left) / 2;
            if (check(powers, k, r, mid))
                left = mid;
            else
                right = mid;
        }
        return left;
    }

    private boolean check(long[] powers, int k, int r, long limit) {
        long cur = 0, count = 0;
        int n = powers.length - 1;

        long[] diff = Arrays.copyOf(powers, powers.length);

        for (int i = 0; i < n; i++) {
            cur += diff[i];
            if (cur < limit) {
                long temp = limit - cur;
                count += temp;
                if (count > k) {
                    return false;
                }
                cur += temp;
                int index = Math.min(n, i + 2 * r + 1);
                diff[index] -= temp;
            }
        }
        return true;
    }
}
